[Coding013] LeetCode 347

Top K Frequent Elements

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

• HashMap元素遍历方法：for (Map.Entry<Integer, Integer> entry : m.entrySet())

• 利用HashMap进行频数统计：m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);

• Java优先权队列的使用：PriorityQueue

• 比较器的内置书写方法和外部实现方法：compare | Comparator

题目：347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

xxxxxxxxxx
2
1
Input: nums = [1,1,1,2,2,3], k = 2
2
Output: [1,2]

Example 2:

xxxxxxxxxx
2
1
Input: nums = [1], k = 1
2
Output: [1]

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

• k is in the range [1, the number of unique elements in the array].

• It is guaranteed that the answer is unique.

代码1（配 · 手绘过程图）

x
1
class Solution {
2
    public int[] topKFrequent(int[] nums, int k) {
3

4
        // 这里注意Map的含义，必须有键值对，所以尖括号<>中，有两个Integer
5
        Map<Integer, Integer> m = new HashMap<>();
6

7
        for (int i = 0; i < nums.length; i++)
8
        {
9
            // 经典HashMap的频数统计代码段
10
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
11
        }
12

13
        // HashMap元素遍历方法：打印所有的键值对，看看里面到底是啥样的！
14
        for (Map.Entry<Integer, Integer> entry : m.entrySet())
15
        {
16
            System.out.println("key = " + entry.getKey() + "; value = " + entry.getValue());
17
        }
18

19
        // 优先权队列：比较器使用内置（Optional）
20
        PriorityQueue<int[]> p = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
21

22
        for (Map.Entry<Integer, Integer> entry : m.entrySet())
23
        {
24
            // 优先权队列的元素增加方法：add()
25
            p.add(new int[]{entry.getKey(), entry.getValue()});
26
            System.out.println("p.size is: " + p.size());
27

28
            // 优先权队列中元素的计数方法：size()
29
            // 优先权队列中元素的出队方法（出的是队尾元素）：poll()
30
            while (p.size() > k)
31
            {
32
                p.poll();
33
            }
34
        }
35

36
        int[] res = new int[k];
37
        for (int i = 0; i < k; i++)
38
        {
39
            // 这句话比较有意思，是一种缩写！
40
            res[i] = p.poll()[0];  // 等价于两句话： int[] temp = p.poll(); res[i] = temp[0];
41
            System.out.println("res ->: " + res[i]);
42
        }
43
        
44
        return res;
45
        
46
    }
47
}

代码解读：

这里的测试样例是

2
1
Input: nums = [11,11,11,11,22,22,22,33,44], k = 2
2
Output: [22,11]

注意1: line20的优先权队列的比较规则，是内置的！

复杂度分析

$O(n)$$O(n)$

代码2（配 · 手绘过程图）

x
1
47
1
class Solution {
2
    public int[] topKFrequent(int[] nums, int k) {
3

4
        // 这里注意Map的含义，必须有键值对，所以尖括号<>中，有两个Integer
5
        Map<Integer, Integer> m = new HashMap<>();
6

7
        for (int i = 0; i < nums.length; i++)
8
        {
9
            // 经典HashMap的频数统计代码段
10
            m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
11
        }
12

13
        // HashMap元素遍历方法：打印所有的键值对，看看里面到底是啥样的！
14
        for (Map.Entry<Integer, Integer> entry : m.entrySet())
15
        {
16
            System.out.println("key = " + entry.getKey() + "; value = " + entry.getValue());
17
        }
18

19
        // 优先权队列：比较器使用内置（Optional）
20
        PriorityQueue<int[]> p = new PriorityQueue<>(
21
            new Comparator<int[]>()
22
            {
23
                public int compare(int[] a, int[] b)
24
                {
25
                    return a[1] - b[1]; // 递减排列的语法
26
                }
27
            }
28
        );
29

30
        for (Map.Entry<Integer, Integer> entry : m.entrySet())
31
        {
32
            // 优先权队列的元素增加方法：add()
33
            p.add(new int[]{entry.getKey(), entry.getValue()});
34
            System.out.println("p.size is: " + p.size());
35

36
            // 优先权队列中元素的计数方法：size()
37
            // 优先权队列中元素的出队方法（出的是队尾元素）：poll()
38
            while (p.size() > k)
39
            {
40
                p.poll();
41
            }
42
        }
43

44
        int[] res = new int[k];
45
        for (int i = 0; i < k; i++)
46
        {
47
            // 这句话比较有意思，是一种缩写！
48
            res[i] = p.poll()[0];  // 等价于两句话： int[] temp = p.poll(); res[i] = temp[0];
49
            System.out.println("res ->: " + res[i]);
50
        }
51
        
52
        return res;
53
        
54
    }
55
}

代码解读：

这里的测试样例是

x
1
Input: nums = [11,11,11,11,22,33,33,33,44], k = 2
2
Output: [33,11]

注意1: line38的while循环，这个循环是嵌套在for循环中间，执行的逻辑是，优先权队列会随时以k为限制条件，控制队列中的元素始终不大于k。

注意2: line20的优先权队列的比较规则，变了！

复杂度分析

$O(n)$$O(n)$

★ 知识点积累 (Java)

1. HashMap相关操作

   xxxxxxxxxx
   11
   1
   // 实例化对象：这里注意Map的含义，必须有键值对，所以尖括号<>中，有两个Integer
   2
   Map<Integer, Integer> m = new HashMap<>();
   3
   
   4
   // 频数统计：经典HashMap的频数统计代码段
   5
   m.put(nums[i], m.getOrDefault(nums[i], 0) + 1);
   6
   
   7
   // 元素遍历：打印所有的键值对
   8
   for (Map.Entry<Integer, Integer> entry : m.entrySet())
   9
   {
   10
       System.out.println("key = " + entry.getKey() + "; value = " + entry.getValue());
   11
   }
   

2. 优先权队列的比较器

   xxxxxxxxxx
   13
   1
   // 优先权队列：比较器使用内置（Optional）
   2
   PriorityQueue<int[]> p = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
   3
   
   4
   // 优先权队列：比较器使用内置（Optional）
   5
   PriorityQueue<int[]> p = new PriorityQueue<>(
   6
       new Comparator<int[]>()
   7
       {
   8
           public int compare(int[] a, int[] b)
   9
           {
   10
               return a[1] - b[1]; // 递减排列的语法
   11
           }
   12
       }
   13
   );
   

3. 优先权队列的相关操作

   x
   10
   1
   // add()
   2
   p.add(new int[]{entry.getKey(), entry.getValue()});
   3
   
   4
   // size()
   5
   while (p.size() > k)
   6
   {
   7
       // poll(): 从队列尾部出队
   8
       int[] t = p.poll();
   9
       System.out.println("value = " + t[0]);
   10
       
   11
       // 上面两句等价于：System.out.println("value = " + p.poll()[0]);
   12
   }